NR‐grep: a fast and flexible pattern‐matching tool
Identifieur interne : 001B21 ( Main/Exploration ); précédent : 001B20; suivant : 001B22NR‐grep: a fast and flexible pattern‐matching tool
Auteurs : Gonzalo Navarro [Chili]Source :
- Software: Practice and Experience [ 0038-0644 ] ; 2001-11-10.
English descriptors
- KwdEn :
Abstract
We present nrgrep (‘non‐deterministic reverse grep’), a new pattern‐matching tool designed for efficient search of complex patterns. Unlike previous tools of the grep family, such as agrep and Gnu grep, nrgrep is based on a single and uniform concept: the bit‐parallel simulation of a non‐deterministic suffix automaton. As a result, nrgrep can find from simple patterns to regular expressions, exactly or allowing errors in the matches, with an efficiency that degrades smoothly as the complexity of the searched pattern increases. Another concept that is fully integrated into nrgrep and that contributes to this smoothness is the selection of adequate subpatterns for fast scanning, which is also absent in many current tools. We show that the efficiency of nrgrep is similar to that of the fastest existing string‐matching tools for the simplest patterns, and is by far unmatched for more complex patterns. Copyright © 2001 John Wiley & Sons, Ltd.
Url:
DOI: 10.1002/spe.411
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002294
- to stream Istex, to step Curation: 002139
- to stream Istex, to step Checkpoint: 001175
- to stream Main, to step Merge: 001C14
- to stream Main, to step Curation: 001B21
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">NR‐grep: a fast and flexible pattern‐matching tool</title><author><name sortKey="Navarro, Gonzalo" sort="Navarro, Gonzalo" uniqKey="Navarro G" first="Gonzalo" last="Navarro">Gonzalo Navarro</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1002/spe.411</idno><idno type="url">https://api.istex.fr/document/84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">002294</idno><idno type="wicri:Area/Istex/Curation">002139</idno><idno type="wicri:Area/Istex/Checkpoint">001175</idno><idno type="wicri:doubleKey">0038-0644:2001:Navarro G:nr:grep:a</idno><idno type="wicri:Area/Main/Merge">001C14</idno><idno type="wicri:Area/Main/Curation">001B21</idno><idno type="wicri:Area/Main/Exploration">001B21</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">NR‐grep: a fast and flexible pattern‐matching tool</title><author><name sortKey="Navarro, Gonzalo" sort="Navarro, Gonzalo" uniqKey="Navarro G" first="Gonzalo" last="Navarro">Gonzalo Navarro</name><affiliation wicri:level="1"><country xml:lang="fr">Chili</country><wicri:regionArea>Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago</wicri:regionArea><wicri:noRegion>Santiago</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="j">Software: Practice and Experience</title><title level="j" type="abbrev">Softw: Pract. Exper.</title><idno type="ISSN">0038-0644</idno><idno type="eISSN">1097-024X</idno><imprint><publisher>John Wiley & Sons, Ltd.</publisher><pubPlace>Chichester, UK</pubPlace><date type="published" when="2001-11-10">2001-11-10</date><biblScope unit="volume">31</biblScope><biblScope unit="issue">13</biblScope><biblScope unit="page" from="1265">1265</biblScope><biblScope unit="page" to="1312">1312</biblScope></imprint><idno type="ISSN">0038-0644</idno></series><idno type="istex">84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D</idno><idno type="DOI">10.1002/spe.411</idno><idno type="ArticleID">SPE411</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0038-0644</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>BNDM</term><term>agrep</term><term>approximate string matching</term><term>grep</term><term>online string matching</term><term>regular expression searching</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We present nrgrep (‘non‐deterministic reverse grep’), a new pattern‐matching tool designed for efficient search of complex patterns. Unlike previous tools of the grep family, such as agrep and Gnu grep, nrgrep is based on a single and uniform concept: the bit‐parallel simulation of a non‐deterministic suffix automaton. As a result, nrgrep can find from simple patterns to regular expressions, exactly or allowing errors in the matches, with an efficiency that degrades smoothly as the complexity of the searched pattern increases. Another concept that is fully integrated into nrgrep and that contributes to this smoothness is the selection of adequate subpatterns for fast scanning, which is also absent in many current tools. We show that the efficiency of nrgrep is similar to that of the fastest existing string‐matching tools for the simplest patterns, and is by far unmatched for more complex patterns. Copyright © 2001 John Wiley & Sons, Ltd.</div></front></TEI><affiliations><list><country><li>Chili</li></country></list><tree><country name="Chili"><noRegion><name sortKey="Navarro, Gonzalo" sort="Navarro, Gonzalo" uniqKey="Navarro G" first="Gonzalo" last="Navarro">Gonzalo Navarro</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001B21 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001B21 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D
|texte= NR‐grep: a fast and flexible pattern‐matching tool
}}
| This area was generated with Dilib version V0.6.32. |  |